In microprocessor based systems (or systems or machines for short), tasks are typically defined by a set (meaning one or more) of high level instructions written in a suitable high level programming language, such as C, C++, Fortran, Basic and JAVA computer programming languages. The strength of high level languages lies in their flexibility allowing the programmers to write programs or code in their own style. The operating systems (such as Unix, Linux and Windows) running in the microprocessor based systems controls the breakdown of the high level instructions into lower level instructions (“native code” or “byte code”) which are executed by the microprocessors. The operating systems also arbitrate cases where contention for the various resources of the systems occurs.
Compilers normally convert (i.e., compile) high level instructions into lower level instructions executable by microprocessors. Compilers are well known art to persons of ordinary skills in the art. The basic components of a compiler are further illustrated by reference to FIG. 1. Referring now to FIG. 1, a language dependent front end 102 of a compiler 100 usually contains a lexical parser, which understands the grammar pertaining to the underlying high level computer programming language. The lexical parser converts high level instructions into logical constructs. At a second stage of the conversion from high level instructions to low level instructions, an optimizer 104 performs loop optimizations, unrolling, etc. At a third stage, a different optimizer 106 performs memory optimizations and management. After the third stage of the conversion, a code generator 108 generates the byte code to be run by a microprocessor.
The scheduling and binding operations of the compiler 100 typically encompass the third and fourth stages, corresponding to the optimizer 106 and the code generator 108. The optimizer 106 and the code generator 108 can be partitioned into hardware and software, depending on a given design. Typically, in systems requiring static code generation, all compiler components are implemented in software, while in systems requiring dynamic code generation, some of the compiler components may be implemented in hardware such as schedulers and binders that take instructions and associate them with actual hardware that will execute those instructions. It should be recognized that implementing components of the compiler 100 in hardware reduces system flexibility and the re-programmability of the machine using a high level language as evidenced in the current art.
One of the components of the compiler 100 is the scheduler which schedules, at compile time, the tasks called for in the code for execution by the target hardware. The scheduling also includes implementing memory management functions such as controlling the use of global and local registers, and the utilization of different levels in memory hierarchy. Typically, tasks are scheduled through the ordering of instructions in a sequence and the insertion of memory references. Normally, the scheduling is static, meaning that once the ordering of instructions cannot be changed once it is set at compilation time.
Another important function of the scheduler is binding. Binding is generally the process of optimizing code execution by associating different properties to a sequence of instructions. For example, in resource binding, a sequence of operations is mapped to the resources required for their execution. If several instructions map to the same hardware for execution, the scheduler, under the resource binding protocol, distributes the execution of the set of instructions by resources based on a given set of constraints to optimize performance. In some instances binding and scheduling are viewed as two separate tasks.
Generally most of the scheduling problems are modeled as ILP (Integer Linear Programming) problems, where the schedule of the required sequence of instructions is decided based on a set of simultaneous linear equations. The scheduler works on the data flow graph (“DFG”) or control flow graph (“CFG”) that is generated in the previous stages of the compilation process. The common types of schedulers in use today are round robin, first in first out, shortest job first, multi-level queue scheduling, priority based scheduling, etc. A highly optimized multi-level priority based scheduler was implemented for a system that is fully set forth in U.S. Pat. No. 7,236,488 which is hereby incorporated by reference.